package anthology.daily_question._25_02;
//https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array/description/?envType=daily-question&envId=2025-02-17
//1287. 有序数组中出现次数超过25%的元素
public class _1287 {
    class Solution {
        public int findSpecialInteger(int[] arr) {
            int length = arr.length;
            if(length == 1){
                return arr[0];
            }
            int sum = length / 4;
            int count = 0, tmp = 0;
            for(int i=0; i<length-1; i++){
                if(arr[i] == arr[i+1]){
                    count++;
                    if(count >= sum){
                        tmp = arr[i];
                        break;
                    }
                }else{
                    count = 0;
                }
            }
            return tmp;
        }
    }
    class Solution2 {
        public int findSpecialInteger(int[] arr) {
            int length = arr.length;
            int l = 0, r = length / 4;
            while (r < length) {
                if (arr[l] == arr[r])
                    return arr[r];
                l++;
                r++;
            }
            return -1;
        }
    }
    class Solution3 {
        public int findSpecialInteger(int[] arr) {
            int n = arr.length;
            int span = n / 4 + 1;
            for (int i = 0; i < n; i += span) {
                int start = binarySearch(arr, arr[i]);
                int end = binarySearch(arr, arr[i] + 1);
                if (end - start >= span) {
                    return arr[i];
                }
            }
            return -1;
        }

        private int binarySearch(int[] arr, int target) {
            int lo = 0, hi = arr.length - 1;
            int res = arr.length;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (arr[mid] >= target) {
                    res = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            return res;
        }
    }
}
